package u1;

import static java.lang.System.*;
import static u1.Util.*;

import gnu.trove.TIntHashSet;

import java.io.InputStream;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;

/**
 * Takes forward links on stdin and produces backward links on stdout. You will
 * need quite a lot of memory to run this.
 */
public class BackwardLinks {
  public static void main(String argv[]) {
    // Do the reversal.
    Map<Integer, TIntHashSet> adj = new BackwardLinks(in, PAGES_MAX)
        .getReversedAdjList();

    // Write it out.
    trace("Done reversal. Writing...");
    new AdjWriter(out).writeT(adj);
    trace("Done.");
  }

  private Map<Integer, TIntHashSet> adj;

  public BackwardLinks(InputStream is, int initialHashCapacity) {
    /*
     * Reverse as we read it in; we can just fit one copy into 8GB of RAM if we
     * use the Trove containers (more efficient than builtins). Make the table
     * big to start to avoid rehashes.
     */
    adj = new HashMap<Integer, TIntHashSet>(initialHashCapacity);
    AdjReader reader = new AdjReader() {

      @Override
      public void readLinks(Integer source, Collection<Integer> targets) {
        for (Integer target : targets) {
          // Add link to hash.
          TIntHashSet targetLinks = adj.get(target);
          if (targetLinks == null) {
            targetLinks = new TIntHashSet();
            targetLinks.add(source); // reverse
            adj.put(target, targetLinks);
          } else if (!targetLinks.contains(source)) {
            targetLinks.add(source); // reverse
          }
        }

        // This can take a while; give feedback.
        if ((getPageIndex() + 1) % 100000 == 0)
          trace("Reversed links for %d pages.", getPageIndex() + 1);
      }

    };
    reader.read(is);
    trace("Reversed %d pages.", reader.getPageIndex());
    trace("Reversed %d links.", reader.getLinkCount());
  }

  public Map<Integer, TIntHashSet> getReversedAdjList() {
    return adj;
  }
}
/*
* Copyright (c) 2009 John Lees-Miller
* 
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
* 
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
* 
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/

